package _4lists.src.DoubleLinkedList;

import java.util.Objects;

public class DoubleLinkedList {

    /**
     * 实际元素个数
     */
    private int size;

    /**
     * 头节点
     */
    private Node first;

    /**
     * 尾节点
     */
    private Node last;

    /**
     * 私有内部类
     */
    private class Node {
        /**
         * 数据
         */
        String data;

        /**
         * 上一个节点
         */
        Node prev;

        /**
         * 下一个节点
         */
        Node next;

        public Node(String data, Node prev, Node next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

    public int getSize() {
        return size;
    }

    public Node getFirst() {
        return first;
    }

    public Node getLast() {
        return last;
    }

    /**
     * 添加元素
     *
     * @param str 要添加的元素
     */
    public void add(String str) {
        // 创建节点
        Node node = new Node(str, null, null);
        // 添加元素分为两种情况
        // 如果当前是第一个节点,那么头节点和尾节点都是同一个
        if (size == 0) {
            this.first = node;
        } else {
            this.last.next = node;
            node.prev = this.last;
        }
        this.last = node;
        size++;
    }

    /**
     * 插入元素
     * @param index  要插入的索引
     * @param str    要插入的数据
     */
    public void add(int index,String str){
        // 判断索引是否越界
        if (index < 0 || index > size) throw new IndexOutOfBoundsException("索引越界");

        // 插入元素分为三种情况
        // 1.插入到尾部  和添加元素方法相同，直接调用添加元素方法
        if (index == size){
            add(str);
            return;
        }
        // 2.插入头部
        // 创建新节点
        Node node = new Node(str,null,null);
        if (index == 0){
            node.next = this.first;
            this.first.prev = node;
            this.first = node;
        }else {
            // 3.插入到中间
            Node no = getNode(index);

            no.prev.next = node;
            node.prev = no.prev;
            node.next = no;
            no.prev = node;
        }
        size++;
    }

    private void out(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException("索引越界");
    }

    /**
     * 删除指定索引处的元素
     * @param index  指定的索引
     */
    public void remove(int index){
        // 判断索引是否越界
        out(index);
        // 1.删除头节点
        if (index == 0){
            this.first = this.first.next;
            this.first.prev = null;
        }else if (index == size - 1){
            // 2.删除尾节点
            this.last = this.last.prev;
            this.last.next = null;
        }else {
            // 删除中间节点
            // 获取指定索引处的节点
            Node no = getNode(index);
            no.prev.next = no.next;
            no.next.prev = no.prev;
        }
        // 实际元素个数-1
        size--;
    }

    /**
     * 根据索引返回索引处的节点
     * @param index  索引
     * @return  节点
     */
    private Node getNode(int index) {
        Node no = first;
        for (int i = 0; i < index; i++) {
            no = no.next;
        }
        return no;
    }

    /**
     * 查询指定元素首次出现的索引
     */
    public int indexOf(String str){
        // 获取头节点
        Node node = this.first;
        // 遍历查询
        for (int i = 0; i < size; i++) {
            if (Objects.equals(node.data,str)){
                return i;
            }
            node = node.next;
        }
        return -1;
    }

    /**
     * 删除指定的元素
     */
    public void remove(String str){
        // 获取元素首次出现的索引
        int index = indexOf(str);
        if (index != -1){
            this.remove(index);
        }
    }

    /**
     * 清空集合
     */
    public void clear(){
        this.first = this.last = null;
        size = 0;
    }

    /**
     * 判断包含指定的元素
     */
    public boolean contains(String str){
        return indexOf(str) != -1;
    }

    /**
     * 获取指定索引处的元素
     */
    public String get(int index){
        // 判断是否越界
        out(index);
        return getNode(index).data;
    }

    /**
     * 判断链表是否为空
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 替换元素
     */
    public void set(int index,String str){
        // 判断是否越界
        out(index);
        // 替换元素
        getNode(index).data = str;
    }

    /**
     * 截取子列表
     * @param fromIndex   开始索引
     * @param toIndex     结束索引
     * @return 新的子列表
     */
    public DoubleLinkedList subList(int fromIndex, int toIndex){
        // 判断是否越界
        out(fromIndex);
        out(toIndex);
        // 判断参数是否合法
        if (fromIndex > toIndex) throw new IllegalArgumentException();

        // 创建子链表
        DoubleLinkedList sublist = new DoubleLinkedList();
        // 获取fromIndex处的节点
        Node node = getNode(fromIndex);
        // 循环添加节点中的元素到新的子链表中
        for (int i = fromIndex;i < toIndex;i++){
            sublist.add(node.data);
            node = node.next;
        }

        return sublist;
    }

    @Override
    public String toString() {
        // 创建拼接字符串对象
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        Node node = first;
        for (int i = 0; i < size; i++) {
            if (i != size - 1){
                stringBuilder.append(node.data).append(", ");
            }else {
                stringBuilder.append(node.data);
            }
            node = node.next;
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
